In a portable communication system, users carry low power, low cost, portable digital radio telephones from place to place during and between calls.
Some portable telephones employ a Digital Signal Processor (DSP) to implement the complicated algorithms that are needed to code speech at low bit rates. Other portable telephones utilize a custom chip for the low bit rate coding of speech and include a low power general purpose microcontroller for handling signalling protocols and other miscellaneous tasks. In either case, the portable telephone must operate for long periods of time on small batteries and a low power implementation of all signal processing operations inside the portable telephone is important. Accordingly, there is a limit on the complexity of any signal processing operation which can take place inside the portable telephone.
In a portable communication system, the portable radio telephones access the local exchange telephone network via a suitably dense matrix of shoebox sized radio ports which are located on utility poles or in buildings. Each port comprises a relatively simple radio modem. Each port is in turn connected back to the telephone network switching system by way of a port control unit which may be located in a central office building. A port control unit performs a variety of processing functions including converting between a format suitable for use on the radio link between the portable telephones and the radio ports and a format suitable for use in the telephone network switching system.
Because a portable communication system transmits conversations between portable telephones and an array of fixed location ports via radio, the conversations of a portable communication system are more susceptible to eavesdropping than are the conversations of a wireline network.
In addition, unlike wireline telephones, which are tied to a particular wire pair on a particular system, portable telephones roam from place to place and access the network via different ports at different times. The lack of association between a user and a particular physical location can make a portable communication system vulnerable to attempts at the fraudulent acquisition of services.
The present invention is particularly concerned with message encryption (i.e. encryption of conversation content), key agreement and distribution (i.e. distribution of the keys required by message encryption techniques) and authentication (i.e. ensuring that a service request is legitimate). In particular, the present invention is concerned with foiling the eavesdropper, i.e., one who utilizes radio equipment to intercept the radio transmissions between the portable telephones and the ports.
Another problem which characterizes portable communication systems is the problem of user traceability. Specifically, if a user transmits identifying information in the clear, it is possible for an eavesdropper to determine the location of the user, so that privacy with respect to a user's location is not maintained. The present invention also relates to maintaining the privacy of a user location. (An existing system, see e.g., ETSI GSM specification, does partially protect the privacy of user locations. But this system requires user/database synchronization, and, under certain circumstances will require user identifying information to be transmitted in the clear via the radio link.)
Eavesdropping can be thwarted through the use of a message encryption technique. A message encryption technique employs an encipherment function which utilizes a number referred to as a session key to encipher data (i.e. conversation content). Only the portable telephone and the specific port control unit with which the portable telephone is in communication have knowledge of the session key, so that only the proper portable telephone and the port control unit, as paired on a particular conversation, can encrypt and decrypt digital signals. Two examples of encipherment functions are the National Bureau of Standards Data Encryption Standard (DES) (see e.g., National Bureau of Standards, "Data Encryption Standard", FIPS-PUB-45, 1977) and the more recent Fast Encipherment Algorithm (FEAL) (see e.g., . Shimizu and S. Miyaguchi, "FEAL-Fast Data Encipherment Algorithm," Systems and Computers in Japan, Vol. 19, No. 7, 1988 and S. Miyaguchi, "The FEAL Cipher Family", Proceedings of CRYPTO '90, Santa Barbara, Calif., Aug., 1990). One way to use an encipherment function is the electronic codebook technique. In this technique a plain text message m is encrypted to produce the cipher text message c using the encipherment function f by the formula c=f(m,sk) where sk is a session key. The message c can only be decrypted with the knowledge of the session key sk to obtain the plain text message m=f.sup.-1 (c,sk).
One problem with the use of the encipherment functions such as DES and FEAL in a portable communication system is the problem of session key agreement.
In the conventional session key agreement technique, each portable telephone i has a secret key k.sub.i known only to it and a cryptographic database DB. Similarly, each port control unit j has a secret key k.sub.j, known only to it and the cryptographic database DB. At the start of a communication session, the portable telephone i sends a service request and its identity i in the clear to a port control unit j. The port control unit sends the pair (i,j) to the cryptographic database DB. The DB picks a random session key sk and sends to the port control unit j the pair c.sub.i,c.sub.j where c.sub.i =f(k.sub.i,SK) and c.sub.j =f(k.sub.j,sk). The port control unit j deciphers c.sub.j to find sk and sends c.sub.i to the portable telephone i. The portable telephone i deciphers c.sub.i to find sk. Now both the port control unit j and the portable telephone i are in possession of the session key sk. Thus, enciphered messages c=f(m,sk) can be transmitted back and forth between the portable telephone i and the port control unit j.
This approach has several advantages. First the approach requires minimal power in the portable telephone because it utilizes only conventional cryptography. In particular, the computation power required to evaluate f and f.sup.-1 is quite small.
In addition, the conventional key distribution approach is also self-authenticating because a portable telephone trying to impersonate the portable telephone i must know the ostensibly secret key k.sub.i ahead of time.
On the other hand, the conventional key distribution protocol requires a database of secret cryptographic keys, which is hard to protect and maintain, and adds survivability and reliability problems to the system. A primary weakness is that a potential eavesdropper can obtain the key k.sub.i for the portable telephone i once, and can subsequently intercept all of i's conversations without i knowing about it. This is the worst kind of damage that can occur; undetectable compromise of privacy. Also, the conventional key distribution protocol has a traceability problem. A portable telephone must announce its identity in the clear before a session key can be fetched from the database. Thus, an eavesdropper can determine the location of a particular portable.
In view of the foregoing, it is an object of the invention to provide a session key agreement protocol which overcomes the shortcomings of the conventional key agreement protocol for a portable communication system. Specifically, it is an object of the invention to utilize public key cryptographic techniques to provide a key agreement protocol for a portable communication system, which protocol eliminates the need for a cryptographic database, authenticates portable telephone identities, and protects as private portable telephone locations.
Before discussing public key cryptographic techniques, it is useful to provide some background information. Most practical modern cryptography is based on two notorious mathematical problems believed (but not proven) to be hard (i.e. not solvable in polynomial time, on the average). The two problems are known as Factorization and Discrete-Log. The Factorization problem is defined as follows:
Input: N, where N=pq where p and q are large prime numbers PA1 Output: p and/or q. PA1 Input: P,g,y, where y.ident.g.sup.x mod P, and P is a large prime number PA1 Output: x. PA1 Input: N,y, where y.ident.x.sup.2 mod N, and N=pq, where p and q are large primes PA1 Output: x PA1 Input: N, g, g.sup.x mod N, g.sup.y mod N, were N.ident.pq and p and q are large primes. PA1 Output: g.sup.xy mod N.
The Discrete-Log problem is defined as follows:
(The Discrete-Log problem can be similarly defined with a composite modulus N=pq).
Based on the Factorization and Discrete-Log problems, some other problems have been defined which correspond to the cracking problems of a cryptographic system.
One example of such a problem which has previously been exploited in cryptography (see, e.g., H. C. Williams, "A Modification of RSA Public-Key Encryption", IEEE Transactions on Information Theory, Vol. IT-26, No. Nov. 6, 1980) is the Modular Square Root problem, which is defined as follows:
Calculating square roots is easy if p and q are known but hard if P and q are not known. When N is composed of two primes, there are in general four square rots mod N. As used herein, z.ident..sqroot.x mod N is defined to mean that x is the smallest integer whereby z.sup.2 .ident.x mod N.
Another problem is known as the Composite Diffie-Hellman (CDH) problem, which is defined as follows:
It has been proven mathematically, that the Modular Square Root and Composite Diffie-Hellman problems are equally difficult to solve as the above-mentioned factorization problem (see, e.g., M. O. Rabin, "Digitalized Signatures and Public Key Functions as Intractable as Factorization", MIT Laboratory for Computer Science, TR 212, Jan. 1979; Z. Shmuely, "Composite Diffie-Hellman Public Key Generating Schemes Are Hard To Break", Computer Science Department of Technion, Israel, TR 356, Feb. 1985; and K. S. McCurley, "A Key Distribution System Equivalent to Factoring", Journal of Cryptology, Vol. 1, No. 2, 1988, pp. 95-105).
How secure is a system based on factorization?. To crack the system, an attacker must factor the composite modulus N-P.q or do another operation of comparable complexity. It has been estimated that factoring a 512-bit number could be done in one year, given an investment on the order of $100 million, given the 1990 state of the art. This is an investment not likely to be made by an eavesdropper trying to intercept routine conversations in a portable communication system.
In a typical public-key cryptographic system, each user i has a public key (e.g. a modulus N) and a secret key (e.g., the factors P and q). A message to user i is encrypted using a public operation which makes use of the public key known to everybody (e.g., squaring a number mod N). However, this message is decrypted using a secret operation (e.g. square root mod N) which makes use of the secret key (e.g., the factors P and q).
This type of public key system has been utilized for message encryption and decryption in a variety of communication systems. However, due primarily to the high computational complexity of previously existing public key cryptographic protocols and given the generally low computational power of portable terminals in a portable communications system, public key cryptographic techniques have not previously been utilized to solve the key agreement and authentication problems in a portable communication system.